/**
 * 冒泡、快速、选择 实现方法不同，但思路都是每次确定一个值的位置
 * 快速排序 用到分治的思想 但需要大量额外的空间 基准数划分
 * 
 * 插入排序 每次得到一个有序的子数组，不断扩增这个数组
 * 希尔排序 不断缩小步长排序
 * 堆排序 通过完全二叉树的特性
 * 归并排序 分治 平分数组分别排序再进行合并
 * 计数排序
 */
/**
 * 冒泡排序
 * 两相比较 每次确定一个最值，缩小范围继续
 * 常见的方法是嵌套循环
 */
function bubbleSort(arr: number[]): number[] {
    const len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    return arr;
}

/**
 * 快速排序
 * 按 基准数 划分 大于基准的组 和 小于基准的组 递归下去
 */
function quickSort(arr: number[]): number[] {
    if (arr.length <= 1) return arr;
    const pivot = arr[arr.length - 1];
    const left = [];
    const right = [];
    for (const el of arr.slice(0, arr.length - 1)) {
        el < pivot ? left.push(el) : right.push(el);
    }
    return [...quickSort(left), pivot, ...quickSort(right)];
}

/**
 * 选择排序
 * 遍历确定 一个最值下标 将其提出来，重复操作
 */
function selectionSort(arr: number[]): number[] {
    const len = arr.length;
    for (let i = 0; i < len; i++) {
        let min = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min !== i) {
            [arr[i], arr[min]] = [arr[min], arr[i]];
        }
    }
    return arr;
}

/**
 * 插入排序
 * 当前的值被缓存 移动数组空出位置 用于插入当前的值
 */
function insertionSort(arr: number[]): number[] {
    const len = arr.length;
    for (let i = 1; i < len; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    return arr;
}

/**
 * 希尔排序
 * 开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。
 */
function shellSort(arr: number[]): number[] {
    let gap = Math.floor(arr.length / 2);
    while (gap >= 1) {
        for (let i = gap; i < arr.length; i++) {
            let j = i;
            const temp = arr[i];
            while (j > gap - 1 && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap = Math.floor(gap / 2);
    }
    return arr;
}

/**
 * 堆排序
 * 依赖 完全二叉树
 */
function heapSort(arr: number[]): number[] {
    let len = arr.length;
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    for (let i = len - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        adjustHeap(arr, 0, i);
    }
    return arr;
}

function adjustHeap(arr: number[], i: number, len: number) {
    let temp = arr[i];
    for (let j = 2 * i + 1; j < len; j = 2 * j + 1) {
        if (j + 1 < len && arr[j] < arr[j + 1]) {
            j++;
        }
        if (arr[j] > temp) {
            arr[i] = arr[j];
            i = j;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

/**
 * 归并排序
 * 分治思想
 */
function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

/**
 * 合并两个两个有序的子序列
 */
function merge(left: number[], right: number[]): number[] {
    let result: number[] = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift() as number);
        } else {
            result.push(right.shift() as number);
        }
    }
    while (left.length) result.push(left.shift() as number);
    while (right.length) result.push(right.shift() as number);
    return result;
}

/**
 * 计数排序
 * 对每个值 进行计数 最后再进行输出
 * 下述写法不支持小数
 */
function countingSort(arr: number[]): number[] {
    let max = Math.max(...arr)
    let min = Math.min(...arr)
    let countArr = new Array(max - min + 1).fill(0);
    arr.forEach(val => countArr[val-min]++);
    let result: number[] = [];
    countArr.forEach((val, index) => {
        for (let i = 0; i < val; i++) {
            result.push(index + min);
        }
    });
    return result;
}

/**
 * 基数排序
 * 基于进制一次比较每一位
 * 下述写法不支持小数、负数
 */
function radixSort(arr: number[]): number[] {
    const maxNum = Math.max(...arr) * 10;
    let divisor = 10;
    while (divisor < maxNum) {
        let buckets = [...Array(10)].map(() => []);
        for (let num of arr) {
            buckets[Math.floor((num % divisor) / (divisor / 10))].push(num);
        }
        arr = [].concat.apply([], buckets);
        divisor *= 10;
    }
    return arr;
}

/**
 * 桶排序
 * 将数据分到有序桶中 再对桶中数据排序
 */
function bucketSort(arr: number[], bucketSize = 5): number[] {
    if (arr.length === 0) {
        return arr;
    }
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;
    let allBuckets = new Array(bucketCount);
    for (let i = 0; i < allBuckets.length; i++) {
        allBuckets[i] = [];
    }
    arr.forEach((num) => {
        allBuckets[Math.floor((num - min) / bucketSize)].push(num);
    });
    return allBuckets.reduce((a, b) => [...a, ...b.sort((a, b) => a - b)], []);
}

exports.sortFn = radixSort